package com.mlh.greed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.IntStream;

/**
 * @author 缪林辉
 * @date 2024/4/15 11:12
 * @DESCRIPTION
 */
// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
// 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
// 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
// 输出：[[1,6],[8,10],[15,18]]
// 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
public class 合并区间 {
    public static void main(String[] args) {
        int[] array = new int[]{1, 4, 6, 7, 2, 34, 5, 65};
        // 想实现升序，规定组合
        // o1<o2 return -1
        // o1=o2 return 0
        // o1>o2 return 1
        // 想实现降序，规定组合
        // o1<o2 return 1
        // o1=o2 return 0
        // o1>o2 return -1
        // 倒序，规定
        // return -1;
        // 不变，规定
        // return 0或者1;
        // 使用流进行降序排序
        int[] sortedArray = IntStream.of(array)
                .boxed() // 转换为 IntegerStream
                .sorted(Collections.reverseOrder()) // 降序排序
                .mapToInt(Integer::intValue) // 转换回 int
                .toArray(); // 转换为数组
        System.out.println(Arrays.toString(sortedArray));
    }


    public int[][] method1(int[][] intervals) {
        // 排序  按照区间的起始排序
        Arrays.sort(intervals, (o1, o2) -> {
            return Integer.compare(o1[0], o2[0]);
        });
        ArrayList<int[]> res = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            //[[1,4],[4,5]] -->[[1,5]]  因此等于也算重叠要合并
            if (end >= intervals[i][0]) {
                if (end < intervals[i][1]) {
                    end = intervals[i][1];
                }
                continue;
            }
            res.add(new int[]{start, end});
            start = intervals[i][0];
            end = intervals[i][1];
        }
        res.add(new int[]{start, end});
        // List转成二维数组
        return res.toArray(new int[res.size()][]);
    }

    public int[][] practice(int[][] intervals) {
        // 先进行排序
        Arrays.sort(intervals, (o1, o2) -> {
            return o1[0] - o2[0];
        });
        int head = intervals[0][0], tail = intervals[0][1];
        List<int[]> res = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (tail >= intervals[i][0]) {// 大于下一个head
                if (tail < intervals[i][1]) {// 小于下一个tail
                    // 更新tail
                    tail = intervals[i][1];
                }
                // 如果tail比下一个区间的尾还大 就不需要更新了
                continue;
            }
            // 如果和下一个区间没重合，则加入到res中，并设置下一个区间为新head和tail
            res.add(new int[]{head, tail});
            head = intervals[i][0];
            tail = intervals[i][1];
        }
        // 最后一个区间需要额外加入，在循环中无法加入
        res.add(new int[]{head, tail});
        return res.toArray(new int[res.size()][]);
    }

    public int[][] practice2(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> {
            return o1[0] - o2[0];
        });
        List<int[]> merge = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int size = merge.size()-1;
            if (size>=0&&merge.get(size)[1] >= intervals[i][0]) {
                if (merge.get(size)[1] < intervals[i][1]) {
                    merge.get(size)[1] = intervals[i][1];
                }
            } else {
                merge.add(intervals[i]);
            }
        }
       return merge.toArray(new int[merge.size()][]);
    }
}
